import java.util.Arrays;

/**
* @description: 1449. 数位成本和为目标值的最大数字
* @author hewei
* @date 2022/10/10 15:26
* @version 1.0
*/

public class LargestNumber2 {

    public static void main(String[] args) {
        int[] cost = {7,6,5,5,5,6,8,7,8};
        System.out.println(new LargestNumber2().largestNumber(cost, 12));
    }

    public String largestNumber(int[] cost, int target) {
        String[] dp = new String[target + 1];
        Arrays.fill(dp, "#");
        dp[0] = "";
        for (int i = cost.length - 1; i >= 0; i--) {
            for (int j = 1; j < target + 1; j++) {
                if (j >= cost[i] && !dp[j - cost[i]].equals("#")) {
                    String s = dp[j - cost[i]] + (char) (i + 1 + '0');
                    if (s.length() == dp[j].length()) {
                        dp[j] = dp[j].compareTo(s) > 0 ? dp[j] : s;
                    } else {
                        dp[j] = dp[j].length() > s.length() ? dp[j] : s;
                    }
                }
            }
        }
        return dp[target].equals("#") ? "0" : dp[target];
    }
}